1. Field of the Invention
The present invention relates to a method for sorting data for polygons and a game machine that employs the method; and in particular, the present invention relates to a method by which a memory area for storing data for polygons can be reduced and high speed sorting of the data for polygons can be performed, and to a game machine that employs that method.
2. Related Arts
In recent video game machines, to provide more realism for users, a figure that is expressed by three-dimensional coordinates is considered as an integrated assembly of a plurality of polygons, and three-dimensional coordinate data for each polygon are transformed into two-dimensional coordinate data for a display device, such as a CRT, that has a two-dimensional display plane. The video game machines use the transformed two-coordinate data for a display on a two-dimensional display plane.
To display polygons in such video game machines, the order in which polygons are to be drawn in a frame buffer memory must be determined based on their relative distances in the direction of the depth of a screen. That is, it is necessary to register data for each polygon in a memory, to sort the data for drawing and read them in the order that corresponds to their relative distances in the direction of the depth of a screen, beginning with data having the greatest distance and to employ the data to draw polygons in the frame buffer memory.
To do this, Quick-Sort, or other sorting sequences are conventionally employed as general sorting methods. By employing such a method, the coordinates of all the polygons are transformed, and the obtained data for polygons are sorted and stored in the order that corresponds to their relative distances in the direction of the depth of a display screen.
With such a general method, after the coordinates of all the polygons are transformed for sorting, it is necessary for the obtained data to be temporarily stored in a memory.
Therefore, a separate, large-capacity memory area is required for the storage of the transformed data. In addition, a procedure is required for the sorting of all the transformed data in descending order from the furthest distance in the direction of depth of a display screen. As the sorting process takes much time, the above described general sorting method is not appropriate for video game machines for which high speed processing is required.
Further, it is of the same situation as the above regarding sorting data for polygons that the data sorted are read out and drawn in a frame memory in the order that corresponds to their relative distances in the direction of the depth of a screen, beginning with data having the smallest distance.